Под термином implicit bias мы будем понимать явление, состоящее в том, что алгоритм обучения среди всех возможных моделей с нулевым эмпирическим риском выбирает определённые. Это явление можно наблюдать уже на очень простом примере. Рассмотрим задачу линейной регрессии с квадратичной функцией потерь. Пусть имеется mm обучающих примеров в евклидовом пространстве размерности N>mN > m. В этом случае наша задача 12Xwy22minw\frac{1}{2} \| X w - y \|_2^2 \to \min_w недоопределена: семейство решений составляет линейное многообразие в пространстве весов. Предположим, что матрица объекты-признаки XRm×NX \in \mathbb{R}^{m \times N} имеет полный ранг по строкам: rkX=m<N\text{rk} X = m < N.

Рассмотрим динамику градиентного спуска с шагом η\eta и нулевой инициализацией весов:

wk+1=wk+ηXT(yXwk),w0=0.w_{k+1} = w_k + \eta X^T (y - X w_k), \quad w_0 = 0.

Нам будет удобнее вместо дискретного градиентного спуска рассматривать его непрерывный аналог

dwdt=XT(yXw),w(t)=0,\frac{dw}{dt} = X^T (y - X w), \quad w(t) = 0,

Вступайте в сообщество хендбука

Здесь можно найти единомышленников, экспертов и просто интересных собеседников. А ещё — получить помощь или поделиться знаниями.

переход к которому соответствует стремлению η\eta к нулю и выбору параметризации по tt, для которой k=[t/η]k = [t / \eta] (округление берётся в любую сторону).

Рассмотрим сингулярное разложение X=UΣVTX = U \Sigma V^T, где UU и VV ортогональны, а Σ\Sigma – прямоугольная диагональная матрица. Тогда

XTX=VΣTΣVTRN×NX^T X = V \Sigma^T \Sigma V^T \in \mathbb{R}^{N \times N}

и rk(XTX)=m\text{rk}(X^T X) = m.

Обозначая w~=VTw\tilde w = V^T w и y~=VTXTy=ΣTUTy\tilde y = V^T X^T y = \Sigma^T U^T y, получаем:

dw~dt=y~ΣTΣw~,w~(0)=0.\frac{d\tilde w}{dt} = \tilde y - \Sigma^T \Sigma \tilde w, \quad \tilde w(0) = 0.

В координатном виде имеем следующее:

dw~idt=y~iσi2w~i,w~i(0)=0i[1:m]\frac{d\tilde w_i}{dt} = \tilde y_i - \sigma_i^2 \tilde w_i, \quad \tilde w_i(0) = 0 \qquad \forall i \in [1:m]

и

dw~idt=0,w~i(0)=0i[m+1:N]\frac{d\tilde w_i}{dt} = 0, \quad \tilde w_i(0) = 0 \qquad \forall i \in [m+1:N]

так как ΣTΣ\Sigma^T \Sigma – диагональная матрица, у которой лишь первые mm элементов на диагонали не равны нулю, и у вектора y~=ΣTUTy\tilde y = \Sigma^T U^T y тоже лишь первые mm координат ненулевые.

Так как все σi\sigma_i для i=1,,mi=1,\ldots,m ненулевые, при tt \to \infty получаем следующее решение:

w~i()=y~iσi2i{1,,m},w~i()=0i{m+1,,N}.\tilde w_i(\infty) = \frac{\tilde y_i}{\sigma_i^2} \quad \forall i \in\{1,\ldots,m\}, \qquad \tilde w_i(\infty) = 0 \quad \forall i \in \{m+1,\ldots,N\}.

Это можно записать в эквивалентном матричном виде: w~()=(ΣTΣ)+y~=Σ+UTy\tilde w(\infty) = (\Sigma^T \Sigma)^+ \tilde y = \Sigma^+ U^T y, где «+» обозначает взятие псевдообратной матрицы.

Значит, w()=VΣ+UTy=X+y=XT(XXT)1yw(\infty) = V \Sigma^{+} U^T y = X^{+} y = X^T (X X^T)^{-1} y в силу того, что матрица XX имеет полный ранг по строкам.

Покажем теперь, что это частное решение, найденное градиентным спуском с нулевой инициализацией, имеет наименьшую евклидову норму среди всех минимумов функции потерь 12Xwy22\frac{1}{2} \vert\vert X w - y \vert\vert_2^2.

Рассмотрим соответствующую функцию Лагранжа:

L(w;λ)=w222+λT(yXw).L(w; \lambda) = \frac{\| w \|_2^2}{2} + \lambda^T (y - X w).

Здесь λRm\lambda \in \mathbb{R}^{m}. Покажем, что пара (w(),λ=(XXT)1y)(w(\infty), \lambda^* = (X X^T)^{-1} y) является критической точкой этой функции:

λL(w();λ)=yXw()=yXXT(XXT)1y=0;\nabla_\lambda L(w(\infty); \lambda^*) = y - X w(\infty) = y - X X^T (X X^T)^{-1} y = 0;

wL(w();λ)=w()XTλ=XT((XXT)1y(XXT)1y)=0.\nabla_w L(w(\infty); \lambda^*) = w(\infty) - X^T \lambda^* = X^T((X X^T)^{-1} y - (X X^T)^{-1} y) = 0.

В силу выпуклости функции Лагранжа эта критическая точка является точкой глобального минимума.

Случай линейных сетей

Каков implicit bias нейронных сетей? Сходится ли градиентный спуск в решение наименьшей нормы и если да, то о какой норме идёт речь? Частичный ответ на этот вопрос удаётся получить для линейных сетей.

Следуя работе Exact solutions to the nonlinear dynamics of learning in deep linear neural networks, рассмотрим линейную сеть с одним скрытым слоем:

f(x;W1:2)=W2W1x,f(x; W_{1:2}) = W_2 W_1 x,

где W1W_1 и W2W_2 – матрицы n×nn\times n.

Поставим задачу многомерной (метка yy – вектор) регрессии с квадратичной функцией потерь:

L(W1:2)=Ex,yyf(x;W1:2)22minW\mathcal{L}(W_{1:2}) = \mathbb{E}_{x,y} \vert\vert y - f(x; W_{1:2}) \vert\vert_2^2 \to \min_W

Шаг градиентного спуска выглядит следующим образом:

W1WT˙=ηEx,yW2T(yxTW2W1xxT),W2WT˙=ηEx,y(yxTW2W1xxT)W1T,\dot{W_1\vphantom{W^T}} = \eta \mathbb{E}_{x,y} W_2^T (y x^T - W_2 W_1 x x^T), \quad \dot{W_2\vphantom{W^T}} = \eta \mathbb{E}_{x,y} (y x^T - W_2 W_1 x x^T) W_1^T,

где точка над WiW_i означает производную по времени (то есть по tt).

Это нелинейная система матричных дифференциальных уравнений второго порядка; чтобы проинтегрировать её аналитически, нам придётся сделать ряд предположений.

Определим ковариационную матрицу входов Σxx=ExxT\Sigma_{xx} = \mathbb{E} x x^T и матрицу ковариации меток со входами Σxy=EyxT\Sigma_{xy} = \mathbb{E} y x^T. Предположим, что данные декоррелированы: Σxx=I\Sigma_{xx} = I; этого можно добиться, заменив входы xx на Σxx1x\Sigma_{xx}^{-1} x. Что касается матрицы ковариации меток со входами, рассмотрим её сингулярное разложение:

Σxy=U2S2,0V0T=r=1nsrurvrT.\Sigma_{xy} = U_2 S_{2,0} V_0^T = \sum_{r=1}^{n} s_r u_r v_r^T.

Назовём srs_r силой моды с индексом rr ковариации между метками и входами.

Сделаем замену координат:

W2=U2TW2,W1=W1V0.\overline{W_2} = U_2^T W_2, \quad \overline{W_1} = W_1 V_0.

В новых координатах градиентный спуск принимает вид:

W˙1=ηW2T(S2,0W2W1),W˙2=η(S2,0W2W1)W1T.\dot{\overline{W}}_1 = \eta \overline{W_2}^T (S_{2,0} - \overline{W_2} \overline{W_1}), \quad \dot{\overline{W}}_2 = \eta (S_{2,0} - \overline{W_2} \overline{W_1}) \overline{W_1}^T.

Пусть W1=[a1,,an]\overline{W_1} = [a_1, \ldots, a_n] и W2=[b1,,bn]T\overline{W_2} = [b_1, \ldots, b_n]^T. Тогда в терминах векторов aa и bb

1ηa˙α=sαbαγ=1nbγ(bγTaα)=(sα(bαTaα))bαγα(bγTaα)bγ;\frac{1}{\eta} \dot a_{\alpha} = s_\alpha b_{\alpha} - \sum_{\gamma=1}^n b_\gamma (b_\gamma^T a_\alpha) = (s_\alpha - (b_\alpha^T a_\alpha)) b_{\alpha} - \sum_{\gamma\neq\alpha} (b_\gamma^T a_\alpha) b_\gamma;

1ηb˙α=sαaαγ=1n(aγTbα)aγ=(sα(aαTbα))aαγα(aγTbα)aγ.\frac{1}{\eta} \dot b_{\alpha} = s_\alpha a_{\alpha} - \sum_{\gamma=1}^n (a_\gamma^T b_\alpha) a_\gamma = (s_\alpha - (a_\alpha^T b_\alpha)) a_{\alpha} - \sum_{\gamma\neq\alpha} (a_\gamma^T b_\alpha) a_\gamma.

Получилась система векторных дифференциальных уравнений порядка 2n2n, всё ещё нелинейная. К счастью, при определённом предположении об инициализации эта система распадается на nn независимых систем порядка 22.

Предположим, что существует ортогональная матрица R=[r1,,rn]R = [r_1, \ldots, r_n], такая что при всех α\alpha имеет место равенство

aα(0)=a~(0)rαa_\alpha(0) = \tilde a(0) r_\alpha и bα(0)=b~(0)rαb_\alpha(0) = \tilde b(0) r_\alpha

для некоторых скалярных величин a~(0)\tilde a(0) и b~(0)\tilde b(0).

Нетрудно заметить, что в этом случае при всех α\alpha и в любой момент времени tt имеем aα(t)=a~(t)rαa_\alpha(t) = \tilde a(t) r_\alpha и bα(t)=b~(t)rαb_\alpha(t) = \tilde b(t) r_\alpha для некоторых скалярных величин a~(t)\tilde a(t) и b~(t)\tilde b(t) .

Тогда для различных α\alpha выражения выше становятся независимыми друг от друга:

da~dt=η(sa~b~)b~,db~dt=η(sa~b~)a~.\frac{d\tilde a}{dt} = \eta (s - \tilde a \tilde b) \tilde b, \qquad \frac{d\tilde b}{dt} = \eta (s - \tilde a \tilde b) \tilde a.

Теперь это система нелинейных дифференциальных уравнений второго порядка.

Если a~=b~\tilde a = \tilde b в начальный момент, то это верно и в любой момент времени. Тогда система выше превращается в одно уравнение первого порядка.

В самом деле, обозначив u=a~b~u = \tilde a \tilde b, получаем:

u˙=2η(su)u.(1)\dot u = 2\eta (s - u) u.\quad(1)

Это уравнение задаёт следующую динамику градиентного спуска для функции потерь E(u)=12(su)2E(u) = \frac{1}{2} (s - u)^2 (её глобальный минимум – это u=su = s).

Перед тем, как интегрировать уравнение (1), напомним, как из uu перейти обратно к исходным W1W_1 и W2W_2. Имеем для W1W_1:

W1=Wˉ1V0T,Wˉ1=[a~r1,,a~rn],a~=u.W_1 = \bar W_1 V_0^T, \qquad \bar W_1 = [\tilde a r_1, \ldots, \tilde a r_n], \qquad \tilde a = \sqrt{u}.

Аналогично для W2W_2:

W2=U2Wˉ2,Wˉ2=[b~r1,,b~rn]T,b~=u.W_2 = U_2 \bar W_2, \qquad \bar W_2 = [\tilde b r_1, \ldots, \tilde b r_n]^T, \qquad \tilde b = \sqrt{u}.

Теперь проинтегрируем уравнение (1) в предположении, что u(0)=u0u(0) = u_0 и u(t)=ufu(t) = u_f для выбранного tt:

t=1ηu0ufdu2u(su)du=12sηu0uf(duu+dusu)du=t = \frac{1}{\eta} \int_{u_0}^{u_f} \frac{du}{2u (s - u)} \, du = \frac{1}{2 s \eta} \int_{u_0}^{u_f} \left(\frac{du}{u} + \frac{du}{s-u}\right) \, du =

=12sη(ln(ufu0)ln(ufsu0s))=12sηln(uf(u0s)u0(ufs)).= \frac{1}{2 s \eta} \left(\ln\left(\frac{u_f}{u_0}\right) - \ln\left(\frac{u_f-s}{u_0-s}\right)\right) = \frac{1}{2 s \eta} \ln\left(\frac{u_f (u_0-s)}{u_0 (u_f-s)}\right).

Рассмотрим время, необходимое, чтобы выучить фиксированную долю силы данной моды uf=ξsu_f = \xi s, где ξ(0,1)\xi \in (0,1), стартуя из точки из окрестности нуля u0=ϵu_0 = \epsilon. Оно равняется

t(ξ)=12sηln(ξ1ξsϵϵ)=12sη(ln(s/ϵ1)ln(ξ11)).t^{(\xi)} = \frac{1}{2 s \eta} \ln\left(\frac{\xi}{1-\xi} \frac{s-\epsilon}{\epsilon}\right) = \frac{1}{2 s \eta} (\ln(s/\epsilon - 1) - \ln(\xi^{-1} - 1)). % \sim \frac{1}{2 s \eta} \ln(s/\epsilon) \; \text{при $\epsilon \to 0$}.

Видим, что чем сильнее мода (то есть чем больше ss), тем быстрее она сходится.

Рассмотрим две моды с силами s1s_1 и s2s_2, такие что s1>s2s_1 > s_2. Насколько вторая (более слабая) мода выучится к моменту, когда первая уже выучится на долю ξ\xi? Из уравнения выше имеем:

uf(u0s)u0(ufs)=e2sηt;\frac{u_f (u_0-s)}{u_0 (u_f-s)} = e^{2 s \eta t};

1suf=(1su0)e2sηt.1 - \frac{s}{u_f} = \left(1 - \frac{s}{u_0}\right) e^{-2 s \eta t}.

Подставляя s=s2s = s_2 и t=t1(ξ)t = t_1^{(\xi)}, получаем:

1s2uf=(1s2ϵ)e2s2ηt1(ξ)=(1s2ϵ)es2s1(ln(s/ϵ1)ln(ξ11))s2ϵ(s1ϵ)s2s1(ξ1ξ)s2s1=s2s1s2s1(ξ1ξ)s2s1ϵs2s11.1 - \frac{s_2}{u_f} = \left(1 - \frac{s_2}{\epsilon}\right) e^{-2 s_2 \eta t_1^{(\xi)}} = \left(1 - \frac{s_2}{\epsilon}\right) e^{-\frac{s_2}{s_1} (\ln(s/\epsilon - 1) - \ln(\xi^{-1} - 1))} \sim\\\sim -\frac{s_2}{\epsilon} \left(\frac{s_1}{\epsilon}\right)^{-\frac{s_2}{s_1}} \left(\frac{\xi}{1-\xi}\right)^{-\frac{s_2}{s_1}} = -s_2 s_1^{-\frac{s_2}{s_1}} \left(\frac{\xi}{1-\xi}\right)^{-\frac{s_2}{s_1}} \epsilon^{\frac{s_2}{s_1} - 1}.

Поскольку s2<s1s_2 < s_1, это выражение стремится к минус бесконечности при ϵ0\epsilon \to 0, из чего следует, что ufu_f стремится к нулю.

Это означает, что если веса в инициализации лежат в окрестности нуля, то к моменту, когда данная мода выучивается на любую фиксированную долю ξ(0,1)\xi \in (0,1), более слабые моды не успевают выучиться вообще. Таким образом, в любой момент времени tt матрица W2(t)W1(t)W_2(t) W_1(t) является наилучшим малоранговым приближением заданного ранга матрицы корреляций Σyx\Sigma_{yx}, причём чем больше tt, тем больше ранг. Можно сказать, что градиентный спуск с фиксированным числом шагов «предпочитает» решения малого ранга.

В выводе выше, мы использовали ряд предположений, в частности, что вектора a1:na_{1:n}, образующие матрицу W1\overline{W_1}, ортогональны в инициализации. Эмпирически те же выводы оказываются верными и без этого предположения, см. графики в оригинальной работе Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. Можно ли их обосновать строго математически? В работах Towards resolving the implicit bias of gradient descent for matrix factorization и Deep Linear Networks Dynamics доказывается, что самая сильная мода выучивается в первую очередь. Тем не менее, на момент написания этого текста остаётся недоказанным, что все моды выучиваются последовательно от сильных к слабым. К сожалению, implicit bias градиентного спуска для нелинейных сетей пока остаётся почти неизученным.

Чтобы добавить в заметки выделенный текст, нажмите Command + E
Загрузка...
Предыдущий параграф13.5. Ландшафт функции потерь
Следующий параграф14.1. Оптимизация в ML

Как найти оптимум функции потерь: от градиентного спуска до Adam